// mathe.cpp
#include "mathe.h"

U64 Gcd(U64 a, U64 b)
{
    // while(a!=b)
    while(1)
    {
        a = a % b;
        if(a == 0) return b;
        b = b % a;
        if(b == 0) return a;
    }
    return a;
}

U64 PowerMod(U64 a, U64 p, U32 m)
{ // 没有大数乘法最高只能计算32位整数的余数
    U64 u64Ret = 1;

    a = a % m;

    while(p > 0)
    {
        if(p % 2 == 1) u64Ret = (u64Ret * a) % m;
        p = p / 2;
        a = (a * a) % m;
    }

    return u64Ret;
}

int U64Bit(U64 a)
{
    int iRet = 0;

    while(a)
    {
        iRet++;
        a >>= 1;
    }

    return iRet;
}

int RootMod(U64& power, U64& index)
{
    int iRet = -1;
    int iResult, iTmp;
    int i;
    double dfBase, dfIndex = index;
    U64 u64Base, u64Pow    = 1;

    if(index <= 0) SET_RET_AND_GOTO_EXIT(COMMON_ERR_INVALIDARGS);

    if(power < 2 || index < 2)
    {
        index = 0;
        SET_RET_AND_GOTO_EXIT(1);
    }
    if(index > 63)
    {
        power = power - 1;
        index = 1;
        SET_RET_AND_GOTO_EXIT(0);
    }

    dfBase  = pow(power, 1.0 / dfIndex);
    u64Base = dfBase;

    for(i = 0; i < index; i++) u64Pow *= u64Base;

    index  = power - u64Pow;
    u64Pow = u64Base;

    iRet = (index == 0);
_Exit:
    return iRet;
}

int IsPower(U64 u64Data)
{
    int iResult, iTmp;
    int iIndex;
    U64 u64Base, u64Re;

    if(u64Data < 4) return (u64Data == 1);

    iIndex = U64Bit(u64Data) - 1;
    while(iIndex > 1)
    {
        u64Base = u64Data;
        u64Re   = iIndex;
        iResult = RootMod(u64Base, u64Re);
        if(iResult) return iIndex;
        iIndex--;
    }

    return 0;
}

U32 MATH_Ord(U64 a, U32 m)
{
    U32 gcd = Gcd(a, m);
    U32 u32Index;

    if(gcd != 1) return 0;

    for(u32Index = 1; u32Index < m; u32Index++)
        if(PowerMod(a, u32Index, m) == 1) return u32Index;

    return 0;
}

U8 Gf256Mul(U8 a, U8 b, U16 u16Poly)
{             // 摘自维基百科
    U8 p = 0; /* the product of the multiplication */
    while(a && b)
    {
        if(b & 1)   /* if b is odd, then add the corresponding a to p (final product = sum of all a's corresponding to odd b's) */
            p ^= a; /* since we're in GF(2^m), addition is an XOR */

        if(a & 0x80) /* GF modulo: if a >= 128, then it will overflow when shifted left, so reduce */
            a = (a << 1) ^ u16Poly;
        else a <<= 1; /* equivalent to a*2 */
        b >>= 1;      /* equivalent to b // 2 */
    }
    return p;
}
